#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=30;
int n,m;
int u,v;
int t;
int a,b,k;
struct Mat{
    int m[N][N];
    Mat(){
        memset(m,0,sizeof(m));
    }
};
Mat mul(Mat a,Mat b){
    Mat t;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            t.m[i][j]=0;
            for(int k=0;k<n;k++){
                t.m[i][j]+=(a.m[i][k]*b.m[k][j])%1000;
            }
        }
    }
    return t;
}
Mat quick_pow(Mat a,int k){
    Mat t;
    for(int i=0;i<n;i++){
        t.m[i][i]=1;
    }
    while(k){
        if(k&1){
            t=mul(t,a);
        }
        k/=2;
        a=mul(a,a);
    }
    return t;
}
int main(void){
    //freopen("data.txt","r",stdin);
    while(~scanf("%d%d",&n,&m) &&(n || m)){
        Mat A,B;
        while(m--){
            scanf("%d%d",&u,&v);
            A.m[u][v]=1;
            //A.m[v][u]=1;
        }
        scanf("%d",&t);
        while(t--){
            scanf("%d%d%d",&a,&b,&k);
            B=A;
            B=quick_pow(A,k);
            printf("%d\n",B.m[a][b]%1000);
        }
    }
    return 0;
}
